{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<font size=6>其它算法</font>\n",
    "# 关联分析\n",
    "关联分析又称关联挖掘，就是在交易数据、关系数据或其他信息载体中，查找存在于项目集合或对象集合之间的频繁模式、关联、相关性或因果结构。\n",
    "关联分析是一种简单、实用的分析技术，就是发现存在于大量数据集中的关联性或相关性，从而描述了一个事物中某些属性同时出现的规律和模式。关联分析的一个典型例子是“购物篮分析”。\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 典型关联分析\n",
    "典型关联分析(Canonical Correlation Analysis，以下简称CCA)是最常用的挖掘数据关联关系的算法之一。\n",
    "\n",
    "在数理统计中，我们使用相关系数来衡量两个序列的关联性。假设有两组一维的数据集X和Y，则相关系数$\\rho$的定义为:\n",
    "$$\\rho(X,Y) = \\frac{cov(X,Y)}{\\sqrt{D(X)}\\sqrt{D(Y)}}$$\n",
    "\n",
    "CCA使用的方法是将多维的$X和Y$都用线性变换为1维的$X'和Y'$，然后再使用相关系数来看$X'和Y'$的相关性。将数据从多维变到1位，也可以理解为CCA是在进行降维，将高维数据降到1维，然后再用相关系数进行相关性的分析。\n",
    "\n",
    "CCA依赖于数据的线性表示，当我们的数据无法线性表示时，CCA就无法使用，此时我们可以利用核函数的思想，将数据映射到高维后，再利用CCA的思想降维到1维，求对应的相关系数和线性关系，这个算法一般称为KCCA。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Apriori算法\n",
    "Apriori算法是常用的用于挖掘出数据关联规则的算法，它用来找出数据值中频繁出现的数据集合，找出这些集合的模式有助于我们做一些决策。\n",
    "### 频繁项集的评估标准\n",
    "#### 支持度\n",
    "$$Support(X,Y) = P(XY) = \\frac{number(XY)}{num(All Samples)}\\\\Support(X,Y,Z) = P(XYZ) = \\frac{number(XYZ)}{num(All Samples)}$$\n",
    "#### 置信度\n",
    "$$Confidence(X,Y) = P(X|Y)=\\frac{P(XY)}{P(Y)}\\\\Confidence(X,Y,Z) = P(X|YZ)=\\frac{P(XYZ)}{P(YZ)}$$\n",
    "#### 提升度\n",
    "$$Lift(X,Y) = \\frac{P(X|Y)}{P(X)} = \\frac{Confidence(X,Y) }{P(X)}$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Apriori算法思想\n",
    "Apriori算法使用支持度来作为判断频繁项集的标准。Apriori算法的目标是找到最大的K项频繁集。这里有两层意思，首先，要找到符合支持度标准的频繁项集。但是这样的频繁集可能有很多。第二层意思要找到最大个数的频繁集。比如我们找到符合支持度的频繁集AB和ABE，那么我们会抛弃AB，只保留ABE，因为AB是2项频繁集，而ABE是3项频繁集。\n",
    "\n",
    "Apriori算法采用了迭代的方法，先搜索出候选1项集及对应的支持度，剪枝去掉低于支持度的1项集，得到频繁1项集。然后对剩下的频繁1项集进行连接，得到候选的频繁2项集，筛选去掉低于支持度的候选频繁2项集，得到真正的频繁二项集，以此类推，迭代下去，直到无法找到满足最小支持度的频繁k+1项集为止，对应的频繁k项集的集合即为算法的输出结果。\n",
    "\n",
    "<img src=\"images/1042406-20170117161036255-1753157633.png\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Apriori算法流程\n",
    "输入：数据集合$D$，支持度阈值$α$\n",
    "\n",
    "输出：最大的频繁$k$项集\n",
    "\n",
    "流程：\n",
    "1. 扫描数据集$D$，得到所有出现过的数据，作为候选频繁1项集。k=1，频繁0项集为空集。\n",
    "2. 挖掘频繁$k$项集\n",
    "    1. 扫描数据计算候选频繁$k$项集的支持度\n",
    "    2. 去除候选频繁$k$项集中支持度低于阈值的数据集,得到频繁k项集。\n",
    "      1. 如果得到的频繁$k$项集为空，则直接返回频繁$k-1$项集的集合作为算法结果，算法结束;\n",
    "      2. 如果得到的频繁$k$项集只有一项，则直接返回频繁k项集的集合作为算法结果，算法结束。\n",
    "    3. 基于频繁$k$项集，连接生成候选频繁k+1项集。\n",
    "3. 令k=k+1，转入步骤2。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Apriori算法总结\n",
    "Apriori算法每轮迭代都要扫描数据集，因此在数据集很大，数据种类很多的时候，算法效率很低。基于经典的Apriori算法衍生了很多算法，包括FP-Tree,GSP, CBA等。这些算法利用了Apriori算法的思想，但是对算法做了改进，数据挖掘效率更好一些。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## FP-Tree\n",
    "FP-tree算法（也称FP Growth算法）采用了一些技巧，无论多少数据，只需要扫描两次数据集，相对于Apriori提高了算法运行的效率。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### FP-Tree数据结构\n",
    "1. 项头表，记录所有1项频繁项集和对应的次数，按照次数降序排列；\n",
    "2. FP Tree，原始数据集映射到内存的一颗FP树（后面详细介绍）；\n",
    "3. 节点链表，依次指向FP树中1项频繁集出现的位置，方便项头表和FP Tree之间联系查找更新；\n",
    "<img src=\"images/1042406-20170119165628718-395589856.png\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 项头表的建立\n",
    "思路：第一次扫描数据，得到所有频繁一项集的的计数。然后删除支持度低于阈值的项，将1项频繁集放入项头表，并按照支持度降序排列。接着第二次也是最后一次扫描数据，将读到的原始数据剔除非频繁1项集，并按照支持度降序排列。\n",
    "<img src=\"images/1042406-20170119161846125-505903867.png\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### FP Tree的建立\n",
    "有了项头表和排序后的数据集，我们就可以开始FP树的建立了。开始时FP树没有数据，建立FP树时我们一条条的读入排序后的数据集，插入FP树，插入时按照排序后的顺序，插入FP树中，排序靠前的节点是祖先节点，而靠后的是子孙节点。如果有共用的祖先，则对应的公用祖先节点计数加1。插入后，如果有新节点出现，则项头表对应的节点会通过节点链表链接上新节点。直到所有的数据都插入到FP树后，FP树的建立完成。\n",
    "<table border=0>\n",
    "    <tr>\n",
    "        <td><img src=\"images/1042406-20170119163935296-1386696266.png\"></td>\n",
    "        <td><img src=\"images/1042406-20170119164235343-504556889.png\"></td>\n",
    "        <td><img src=\"images/1042406-20170119165253265-145701384.png\"></td>\n",
    "    </tr>\n",
    "    <tr>\n",
    "        <td><img src=\"images/1042406-20170119165307640-1886233741.png\"></td>\n",
    "        <td><img src=\"images/1042406-20170119165315890-467841267.png\"></td>\n",
    "        <td><img src=\"images/1042406-20170119165326484-481251658.png\"></td>  \n",
    "    </tr>\n",
    "    <tr>\n",
    "        <td><img src=\"images/1042406-20170119165335968-745891027.png\"></td>\n",
    "        <td><img src=\"images/1042406-20170119165346437-1176754608.png\"></td>  \n",
    "        <td><img src=\"images/1042406-20170119165356531-138078582.png\"></td> \n",
    "    </tr>\n",
    "    <tr>\n",
    "        <td><img src=\"images/1042406-20170119165427593-1237891371.png\"></td>      \n",
    "    </tr>\n",
    "</table>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### FP Tree的挖掘\n",
    "得到了FP树和项头表以及节点链表，我们首先要从项头表的底部项依次向上挖掘。对于项头表对应于FP树的每一项，我们要找到它的条件模式基。所谓条件模式基是以我们要挖掘的节点作为叶子节点所对应的FP子树。得到这个FP子树，我们将子树中每个节点的的计数设置为叶子节点的计数，并删除计数低于支持度的节点。从这个条件模式基，我们就可以递归挖掘得到频繁项集了。\n",
    "<table border=0>\n",
    "    <tr>\n",
    "        <td><img src=\"images/1042406-20170119170723421-1812925376.png\"></td>\n",
    "        <td><img src=\"images/1042406-20170119171924093-1331841220.png\"></td>\n",
    "    </tr>\n",
    "    <tr>\n",
    "        <td><img src=\"images/1042406-20170119205610265-1248946944.png\"></td>\n",
    "        <td><img src=\"images/1042406-20170119205839703-739252492.png\"></td>\n",
    "    </tr>\n",
    "    <tr>\n",
    "        <td><img src=\"images/1042406-20170119210046375-59327550.png\"></td>      \n",
    "        <td><img src=\"images/1042406-20170119210254812-1959388744.png\"></td>    \n",
    "    </tr>\n",
    "</table>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### FP-Tree流程\n",
    "1. 扫描数据，得到所有频繁1项集的的计数。然后删除支持度低于阈值的项，将1项频繁集放入项头表，并按照支持度降序排列。\n",
    "2. 扫描数据，将读到的原始数据剔除非频繁1项集，并按照支持度降序排列。\n",
    "3. 读入排序后的数据集，插入FP树，插入时按照排序后的顺序，插入FP树中，排序靠前的节点是祖先节点，而靠后的是子孙节点。\n",
    "    1. 如果有共用的祖先，则对应的公用祖先节点计数加1。\n",
    "    2. 插入后，如果有新节点出现，则项头表对应的节点会通过节点链表链接上新节点。\n",
    "    3. 直到所有的数据都插入到FP树后，FP树的建立完成。\n",
    "4. 从项头表的底部项依次向上找到项头表项对应的条件模式基。从条件模式基递归挖掘得到项头表项项的频繁项集。\n",
    "5. 如果不限制频繁项集的项数，则返回步骤4所有的频繁项集，否则只返回满足项数要求的频繁项集。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### FP-tree算法总结\n",
    "FP Tree算法改进了Apriori算法的I/O瓶颈，巧妙的利用了树结构。在实践中，FP Tree算法是可以用于生产环境的关联算法，而Apriori算法则做为先驱，除了FP Tree，像GSP，CBA之类的算法都是Apriori派系的。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 推荐算法\n",
    "推荐算法具有非常多的应用场景和商业价值。推荐算法种类很多，但是目前应用最广泛的应该是协同过滤类别的推荐算法。\n",
    "\n",
    "## 种类\n",
    "1. 基于内容的推荐\n",
    "1. 协调过滤推荐\n",
    "1. 混合推荐\n",
    "1. 基于规则的推荐\n",
    "1. 基于人口统计信息的推荐"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 协同过滤推荐\n",
    "协同过滤(Collaborative Filtering)作为推荐算法中最经典的类型，包括在线的协同和离线的过滤两部分。\n",
    "\n",
    "协同过滤的模型一般为m个物品，m个用户的数据，只有部分用户和部分数据之间是有评分数据的，其它部分评分是空白，此时我们要用已有的部分稀疏数据来预测那些空白的物品和数据之间的评分关系，找到最高评分的物品推荐给用户。\n",
    "\n",
    "一般来说，协同过滤推荐分为三种类型：\n",
    "1. 基于用户(user-based)，\n",
    "1. 基于项目(item-based)，\n",
    "1. 基于模型(mode-based)。\n",
    "    1. 用关联算法；\n",
    "    2. 用聚类算法；\n",
    "    3. 用分类算法；\n",
    "    4. 用回归算法；\n",
    "    5. 用矩阵分解；\n",
    "    6. 用神经网络；\n",
    "    7. 用隐语义模型"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 协同过滤总结　\n",
    "协同过滤作为一种经典的推荐算法种类，在工业界应用广泛，它的优点很多，模型通用性强，不需要太多对应数据领域的专业知识，工程实现简单，效果也不错。\n",
    "\n",
    "协同过滤也有些难以避免的难题，比如令人头疼的“冷启动”问题，没有新用户任何数据的时候，无法较好的为新用户推荐物品。同时也没有考虑情景的差异，比如根据用户所在的场景和用户当前的情绪。当然，也无法得到一些小众的独特喜好，这块是基于内容的推荐比较擅长的。　　　"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 迁移学习\n",
    "所谓迁移学习，或者领域适应Domain Adaptation，一般就是要将从源领域（Source Domain）学习到的东西应用到目标领域（Target Domain）上去。\n",
    "## 基本概念\n",
    "域：一个域 $D$ 由一个特征空间 $X$ 和特征空间上的边际概率分布 $P(X)$ 组成，其中$ X=x_1,x_2,\\dots,x_n$ 。\n",
    "\n",
    "任务 ：在给定一个域 $D=\\{X,P(X)\\}$ 之后，一个任务 $T$ 由一个标签空间 $y$ 以及一个条件概率分布$ P(Y/X)$ 构成，其中，这个条件概率分布通常是从由特征—标签对 $x_i, y_i$组成的训练数据中学习得到。\n",
    "\n",
    "源域(source domain),目标域(target domain):在迁移学习中，我们已有的知识叫做源域(source domain)，要学习的新知识叫目标域(target domain)。\n",
    "\n",
    "负迁移:指的是在源域上学习到的知识，对于目标域上的学习产生负面作用。产生负迁移的原因主要有两个：一个是源域 和目标域的相似度很低，无法做迁移。另一个是虽数据问源域和目标域是相似的，但是，迁移学习方法不够好，没找到可迁移的成分，导致负迁移。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 简介和定义\n",
    "迁移学习，类比于我们已经会编写Java程序，就可以类比着来学习C++，都是面向对象的语言，就很快学会了，或者在学会骑自行车之后，骑摩托车也自己比较容易了，因为这两种交通工具有许多相似之处。\n",
    "\n",
    "严格定义：给定源域 $D_s=\\{X_s, F_s(X_s)\\}$ 和学习任务$ T_s $,目标域 $D_t=\\{X_t,F_t(X_t)\\}$ 和学习任务$ T_t$ ,迁移学习旨在源域不同于目标域或学习任务$ T_t$ 不同于学习任务 $T_s$ 的条件下通过使用学习任务$ T_s$ 和源域$D_s=\\{X_s, F_s(X_s)\\}$所获取的知识来帮助学习目标的在目标域$D_t$的预测函数 $F_t$ 。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 为什么需要进行迁移学习？\n",
    "1. 数据的标签很难获取，当有些任务的数据标签很难获取时，就可以通过其他容易获取标签且和该任务相似的任务来迁移学习。\n",
    "2. 从头建立模型是复杂和耗时的，也即是需要通过迁移学习来加快学习效率。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 迁移学习的分类\n",
    "### 按迁移情景\n",
    "1. 归纳式迁移学习（Inductive TL）：源域和目标域的学习任务不同\n",
    "1. 直推式迁移学习（Transductive TL):源域和目标域不同，学习任务相同\n",
    "1. 无监督迁移学习（Unsupervised TL):源域和目标域均没有标签\n",
    "<img src=\"images/5e71000248b90fbbd19a.jfif\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 按基本方法分\n",
    "#### 基于实例\n",
    "<img src=\"images/5e71000248bb6228e335.jfif\">\n",
    "\n",
    "#### 基于特征\n",
    "<img src=\"images/5b5c00031a2055153171.jfif\">\n",
    "\n",
    "#### 基于模型\n",
    "<img src=\"images/5e7100024fcac33a5c82.jfif\">\n",
    "\n",
    "#### 基于关系\n",
    "<img src=\"images/5e71000248b885022aa6.jfif\">\n",
    "\n",
    "#### 总结\n",
    "<img src=\"images/5b5b00037820d27209ae.jfif\">\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 按特征空间分\n",
    "1. 同构迁移学习（Homogeneous TL）: 源域和目标域的特征维度相同分布不同\n",
    "1. 异构迁移学习（Heterogeneous TL）：源域和目标域的特征空间不同"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 总结\n",
    "<img src=\"images/5e71000248b78d25aaa5.jfif\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#  强化学习\n",
    "强化学习：Reinforcement Learning，又称再励学习或者评价学习。智能系统从环境到行为映射的学习，以使奖励信号（强化信号）函数值最大，由于外部给出的信息很少，强化学习系统必须依靠自身的经历进行自我学习。通过这种学习获取知识，改进行动方案以适应环境。强化学习最关键的三个因素是状态，行为和环境奖励。谷歌的AlphaZero.\n",
    "<img src=\"images/20170106092855016.jfif\">"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.3"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {
    "height": "606.979px",
    "width": "514.282px"
   },
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  },
  "varInspector": {
   "cols": {
    "lenName": 16,
    "lenType": 16,
    "lenVar": 40
   },
   "kernels_config": {
    "python": {
     "delete_cmd_postfix": "",
     "delete_cmd_prefix": "del ",
     "library": "var_list.py",
     "varRefreshCmd": "print(var_dic_list())"
    },
    "r": {
     "delete_cmd_postfix": ") ",
     "delete_cmd_prefix": "rm(",
     "library": "var_list.r",
     "varRefreshCmd": "cat(var_dic_list()) "
    }
   },
   "types_to_exclude": [
    "module",
    "function",
    "builtin_function_or_method",
    "instance",
    "_Feature"
   ],
   "window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
